package leetcode._08_dynic;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author pppppp
 * @date 2022/3/23 13:57
 * 给定一个正整数、负整数和 0 组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。
 * 返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，
 * r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。
 * 注意：本题相对书上原题稍作改动
 * <p>
 * 示例
 * 输入：
 * [
 *    [-1,0],
 *    [0,-1]
 * ]
 * 输出：[0,1,0,1]
 * 解释：输入中标粗的元素即为输出所表示的矩阵
 * 说明：
 * 1 <= matrix.length, matrix[0].length <= 200
 */
public class _17_24_最大子矩阵 {

    /*二维求和转化为一维数组的最大连续子序列的和*/
    @Test
    public void T_1() {
        // int [][] nums = {{-1,0},{0,-1}};
        int[][] nums = {{1, 2}, {3, 4}, {1, 2}};
        System.out.println(getMaxMatrix(nums));
    }

    public int[] getMaxMatrix(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        int[] b = new int[m];
        int maxRes = Integer.MIN_VALUE;
        int[] res = new int[4];
        Arrays.fill(res, -1);
        for (int r = 0; r < n; r++) {
            Arrays.fill(b, 0);
            /*求解 以第r行 为首行的所有列累加和形成的一维数组 连续最大子序列和*/
            for (int i = r; i < n; i++) {
                /*求解 第i行 连续最大子序列和*/
                int sum = 0;
                int leftCol = 0;
                for (int j = 0; j < m; j++) {
                    b[j] += matrix[i][j];
                    if (sum > 0) {
                        sum += b[j];
                    } else {
                        sum = b[j];
                        leftCol = j;
                    }
                    if (sum > maxRes) {
                        maxRes = sum;
                        res[0] = r;
                        res[1] = leftCol;
                        res[2] = i;
                        res[3] = j;
                    }
                }
            }
        }
        return res;
    }
}
